The present invention relates to a method and apparatus for comparing two or more patterns to determine whether they are the same or essentially the same. The invention accommodates changes in size, including both linear and nonlinear warping, segmentation of either or both patterns, the addition of visual noise, local changes, and variations due to sensor conditions such as resolution and focus. The inventor has coined the term "flash correlation" to describe the method of comparison, which is inherently parallel and involves a single operation.
Flash correlation artifacts which are produced by the present invention also provide cues to quantitative assessment of relative stretching, blurring, and warping of one image with respect to the other. The existence and behavior of the flash correlation artifacts (FCAs), as well as other features of flash correlation, distinguish it from moire' patterns. Generally, moire' effects occur as a result of superimposed repeated patterns. The effects vary with angle, but generally occur throughout the overlaid images. Any two overlaid images of repetitive line patterns will produce moire' effects; therefore, the existence of a moire' effect does not indicate a match between patterns.
Patterns comprised of dots or of naturally occurring grains have been used to encode information for more than 25 years. The patterns can be generated through chemical, mechanical, photographic, or manual dispersals of particles. Carlson [U.S. Pat. No. 3,279,095 October 1966] uses photographic grains as a pseudo-random naturally occurring pattern which can be reproduced, with local photographic reversals, and used to transmit information hidden by the grain patterns. The recipient subsequently uses an overlay created photographically to unmask the embedded information. Carlson's technique required that the original and overlay be the same size and be registered exactly in order to read the information. The technique applies only to readout of a single embedded message in an image using a single overlay constructed for that image.
Cook [U.S. Pat. No. 4,682,954, July 1987] encodes a sheet of pictorial information by using one mask formed by random opaque and transparent areas, and a second mask which is the complement of the first. By photographically exposing the information through each of the two masks, the information is separated into two images which each appear to be randomized; however, the combination of the two, with precise registration and identical size, allows the original information to be read. The technique applies to readout of a single image.
Falvin et al. [U.S. Pat. No. 4,544,836, October 1985] utilize binary optical encoding techniques to generate cards for use in access control systems. Use of sandwiched layers of material prevents human viewing of the optical code without destroying the card. The access control card reader contains appropriate illumination sources to make the code visible. Bar code reading techniques are then employed to reject or accept the card. The sandwiched layers may pertain to different optical frequencies for enhanced security against counterfeit cards. Information density is not great, and precise registration is not required. Only one card at a time is read.
Winters [U.S. Pat. No. 4,586,711, May 1986] applies randomly encoded masks to generate matching cards for game applications. Employing the basic techniques of Carlson and Cook, Winters uses computer-generated binary images to create 2-card sets which overlaid together create visible images. Mass distribution of random cards, only one or a few of which match a "prize" card, can then be used for games of chance and advertising promotions. Only one possible card is compared at a time to the "prize" card. Precise registration and identical size are required.
Dlugos [U.S. Pat. No. 4,660,221, April 1987] utilizes a binary mask applied to printed characters to authenticate the characters. The mask may be varied with each use for additional security. In the intended application to authenticating postal franking machine printing, the result is to impose voids in the printed characters, where the pattern of voids can be used to authenticate the franking. Authentication involves reading out the voids in each location. Precise registration and identical size are required. Also, each void of a single image is decoded in series.
Kafri et al. [U.S. Pat. No. 4,776,013, October 1988] encode optical images by converting them to a grid of pixels where each pixel has a grey level value from at least two allowed values. The encoding is performed either optically or digitally by transmitting for each image pixel the intensity value of a master matrix, or a random value, depending on the value of the image pixel. Decoding requires use of the master matrix, and requires precise alignment between it and the transmitted encoded image. The technique applies to readout of a single image.
Others have applied similar techniques to the transmission of information via facsimile machine or over other channels. Readout of the information requires the use of a matching mask or overlay